package daily.year2024.m9;

/**
 * 位运算
 * 338.比特位计数
 *
 * @author wjs 2024/9/28
 */
public class d28 {
    //解法1：
    //使用位运算统计+缓存
    class Solution1 {
        int[] cache = new int[100001];

        public int[] countBits(int n) {
            int[] res = new int[n+1];
            for(int i=1;i <= n;i++) {
                if(cache[i] != 0) {
                    res[i] = cache[i];
                } else {
                    res[i] = countBit(i);
                    cache[i] = res[i];
                }
            }
            return res;
        }
        private int countBit(int n) {
            int bit = 1, cnt = 0, res = 0;
            while(cnt < 32) {
                if((n & bit) != 0) {
                    res++;
                }
                bit <<= 1;
                cnt++;
            }
            return res;
        }
    }

    //解法2：
    //使用Brian Kernighan算法
    //原理是通过使用 n & (n-1) 来消除掉二进制位中的最后一位1
    class Solution2 {
        int[] cache = new int[100001];

        public int[] countBits(int n) {
            int[] res = new int[n+1];
            for(int i=1;i <= n;i++) {
                if(cache[i] == 0) {
                    cache[i] = countBit(i);
                }
                res[i] = cache[i];
            }
            return res;
        }
        private int countBit(int n) {
            int res = 0;
            while(n != 0) {
                n = n & (n-1);
                res++;
            }
            return res;
        }
    }

    //解法3：
    //最高有效位+动态规划+快速确定整数是否为2的整数次幂
    class Solution3 {
        public int[] countBits(int n) {
            int[] dp = new int[n+1];
            int highBit = 0;
            for(int i=1;i <= n;i++) {
                if((i & (i-1)) == 0) {
                    highBit = i;
                }
                dp[i] = dp[i-highBit] + 1;
            }
            return dp;
        }
    }

    //解法4：
    //最低有效位+动态规划
    class Solution4 {
        public int[] countBits(int n) {
            int[] dp = new int[n+1];
            for(int i=1;i <= n;i++) {
                dp[i] = dp[i>>1] + (i&1);
            }
            return dp;
        }
    }
}
